package HOT;

/**
 * Author  zxy
 * Date  2023/7/12 10:23
 */

/*
* 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中
* 除 nums[i] 之外其余各元素的乘积 。
* 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
* 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
* */

public class ProductExceptSelf_238 {
    public int[] productExceptSelf(int[] nums) {

        int len = nums.length;

        // O(n) 空间复杂度
        /*
        int[] preMul = new int[len + 2];
        int[] sufMul = new int[len + 2];

        preMul[0] = preMul[len + 1] = 1;
        sufMul[0] = sufMul[len + 1] = 1;


        // 计算前缀和后缀乘积
        for (int i = 0; i < len; i++) {
            preMul[i + 1] = preMul[i] * nums[i];

            int sufIndex = len - i;
            sufMul[sufIndex] = sufMul[sufIndex + 1] * nums[sufIndex - 1];
        }

        int[] ret = new int[len];

        // System.out.println(Arrays.toString(preMul));
        // System.out.println(Arrays.toString(sufMul));

        for (int i = 0; i < len; i++) {
            ret[i] = preMul[i] * sufMul[i + 2];
        }

        return ret;
        */


        // O(1)
        int[] ret = new int[len];

        // 计算前缀和
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                ret[i] = nums[i];
            } else {
                ret[i] = ret[i - 1] * nums[i];
            }
        }

        // 计算后缀和
        for (int i = len - 1; i >= 0; i--) {
            if (i != len - 1) {
                nums[i] *= nums[i + 1];
            }
        }

        // System.out.println(Arrays.toString(ret));
        // System.out.println(Arrays.toString(nums));

        // 前后缀乘积
        for (int i = len - 1; i >= 0; i--) {
            if (i == 0) {
                ret[i] = nums[i + 1];
            } else if (i < len - 1) {
                ret[i] = ret[i - 1] * nums[i + 1];
            } else {
                ret[i] = ret[i - 1];
            }
        }

        return ret;
    }
}

